package main

import "fmt"

// TreeNode struct
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	arr1 := []int{1, 2, 3}
	arr2 := []int{3, 2, 1}
	res := buildTree(arr1, arr2)
	fmt.Println(res)
}

func buildTree(inorder []int, postorder []int) *TreeNode {
	indexMap := map[int]int{}
	for i, v := range inorder {
		indexMap[v] = i
	}
	var build func(inorderLeft, inorderRight int) *TreeNode
	build = func(inorderLeft, inorderRight int) *TreeNode {
		if inorderLeft > inorderRight {
			return nil
		}

		val := postorder[len(postorder)-1]
		postorder = postorder[:len(postorder)-1]
		root := &TreeNode{Val: val}
		inorderRootIndex := indexMap[val]
		root.Right = build(inorderRootIndex+1, inorderRight)
		root.Left = build(inorderLeft, inorderRootIndex-1)
		return root
	}
	return build(0, len(inorder)-1)
}
